package com.yeban.base.day05.homework;

import java.util.Arrays;

/**
 * @Desc TODO
 * @Author yeban
 * @Date 2025/9/29
 */
// 快速排序
public class Test02 {

    public static void QuickSort(int[] arr, int left, int right) {

        if( left >= right) {
            return;
        }

        if (left < right) {
            int pivot = partition(arr, left, right);
            //递归
            QuickSort(arr, left, pivot - 1);
            QuickSort(arr, pivot + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {

        // 分区操作
        // temp临时坑位，默认为左边的第一个
        int temp = arr[left];

        // 快速排序循环
        while(left < right) {

            while(left < right && arr[right] >= temp) {
                arr[left] = arr[-- right];
            }

            while(left < right && arr[left] <= temp) {
                arr[right] = arr[++ left];
            }
        }

        arr[left] = temp;
        return left;
    }

    public static void main(String[] args) {

        int[] arr = { 8, 26, 12, 29, 10, 27, 47 };
        System.out.println("快速排序前：" + Arrays.toString(arr));

        QuickSort(arr, 0, arr.length - 1);

        System.out.println("快速排序后：" + Arrays.toString(arr));

    }
}
